package sort

/*
	k 桶的个数
	平均时间复杂度：O(n+k)
	最好情况：O(n+k)
	最坏情况：O(n²)
	空间复杂度：O(n)
	排序方式：InPlace
	稳定性：稳定
*/
func BucketSort(nums []int) {

	if len(nums) <= 0 {
		return
	}

	max, min := nums[0], nums[0]
	for _, v := range nums {
		if v > max {
			max = v
		} else if v < min {
			min = v
		}
	}

	var bucketnums int = (max-min)/len(nums) + 1
	buckets := make([][]int, bucketnums)
	for i := 0; i < bucketnums; i++ {
		buckets[i] = make([]int, 0)
	}

	// 放入桶
	for _, v := range nums {
		index := (v - min) / len(nums)
		buckets[index] = insert(buckets[index], v)
	}

	index := 0
	for _, b := range buckets {
		for _, v := range b {
			nums[index] = v
			index++
		}
	}

}

func insert(nums []int, num int) []int {

	if len(nums) == 0 {
		return append(nums, num)
	}

	length := len(nums)
	temp := num
	nums = append(nums, 0)

	for i := length - 1; i >= 0; i-- {
		if temp < nums[i] {
			nums[i+1] = nums[i]
			if i == 0 {
				nums[i] = temp
			}
		} else {
			nums[i+1] = temp
			break
		}
	}

	return nums

}
